package leetcode.LinkedList;

/**
 * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
 * <p>
 * 图示两个链表在节点 c1 开始相交：
 * <p>
 * <p>
 * <p>
 * 题目数据 保证 整个链式结构中不存在环。
 * <p>
 * 注意，函数返回结果后，链表必须 保持其原始结构 。
 * <p>
 * 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author wangmaolin1
 * @date 2021/11/28 下午5:31
 */
public class _160相交链表 {
    /*
      关键点：  如果相交，则从相交的开始，往后的长度一模一样，因此计算两个链表的长度，如果不一致，则计算出差长diff，
      让长的链表的起始节点从 head 往后挪diff 个，然后依次比较，当出现相同的节点的时候，则返回该节点，当任意一个节点为 null 了，说明没有相交，返回 null
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null) {
            return null;
        }
        if (headB == null) {
            return headA;
        }
        ListNode tempA = headA;
        ListNode tempB = headB;
        int lenA = getLength(tempA);
        int lenB = getLength(tempB);
        //相差的长度
        int diff = lenA > lenB ? lenA - lenB : lenB - lenA;
        tempA=headA;
        tempB=headB;
        if (lenA>lenB){
            for (int i = 0; i < diff; i++) {
                tempA=tempA.next;
            }
        }else {
            for (int i = 0; i < diff; i++) {
                tempB=tempB.next;
            }
        }
        while (tempB!=tempA){
            tempA=tempA.next;
            tempB=tempB.next;
            if (tempA==null||tempB==null){
                break;
            }
        }
        if (tempA==null||tempB==null){
            return null;
        }
        return tempA;

    }
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        if (headA == null){
            return headB;
        }
        if (headB == null){
            return  headA;
        }
        ListNode h1=headA;
        ListNode h2=headB;
        while (h1!=h2){
            if (h1==null){
                h1=headB;
            }else {
                h1=h1.next;
            }
            if (h2==null){
                h2=headA;
            }else {
                h2=h2.next;
            }
        }
        return h1;
    }
    private int getLength(ListNode headA) {
        int len = 0;
        while (headA != null) {
            len++;
            headA = headA.next;
        }
        return len;
    }

}
